package suanfa;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SumOfThreeNumbers {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret=new ArrayList<>();
        Arrays.sort(nums);
        int n=nums.length;
        for(int i=0;i<n;){
            if(nums[i]>0) break;
            int left=i+1,right=n-1,target=-nums[i];
            while(left<right){
                int sum=nums[left]+nums[right];
                if(sum>target) right--;
                else if(sum<target) left++;
                else{
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                    left++;right--;
                    while(left<right && nums[left]==nums[left-1]) left++;
                    while(left<right && nums[right]==nums[right+1]) right--;
                }
            }
            i++;//如果i++在循环上面，假设进入到这个while循环里面了，i++，当再次进入循环时，会再次自增i++，
            //导致漏掉一个数
            //假设数组是：[-1, -1, 0, 1, 2]
            //当 i = 0 时，程序正常运行；
            //当 i = 1 时，由于 nums[1] == nums[0]，进入 while(i < n && nums[i] == nums[i-1]) i++，此时 i 被再次自增变成 2；
            //但是 for 循环还会再执行一次 i++ → 最终 i = 3，中间的 i = 2 被跳过了！
            while(i<n && nums[i]==nums[i-1]) i++;
        }
        return ret;
    }
}
